# Graham Scan

• 2026년 7월 8일 알고리즘
  볼록 껍질 ② — Graham Scan과 정렬 하한

  Package Wrapping은 걸음마다 점 전체를 훑어 최악 O(N²)이다. Graham Scan은 각도 정렬 한 번 뒤 스택으로 좌회전만 남겨 O(N log N)에 볼록 껍질을 구한다. 정렬을 볼록 껍질로 환원해 Ω(N log N) 하한까지 확인한다.